//	INM359: Object-Oriented Programming in C++ Coursework
//	Blair Trusler - Blair.Trusler.1@city.ac.uk

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>

using namespace std;

//Graph Class: stores nodes and edges of an inputted graph and calculates the shortest path between a start and end node
template <typename NodeType>
class Graph{
public:
	void createNode(const NodeType &node);
	double createEdge(const NodeType &nodeA, const NodeType &nodeB, const double &edgeCost);
	int numberOfNodes();
	int checkNodes(const NodeType &node);
	int returnNodeNumber(const NodeType &nodeLabel);
	NodeType returnNodeLabel(const int &nodeNum);
	vector<pair<double, NodeType> > dijkstraAlgorithm(const NodeType &startNode, const NodeType &endNode);
private:
	map<NodeType, int> mapNodes;			//Map containing node as the key value mapped to an integer
	vector<NodeType> vectorNodes;			//Vector of graph nodes
	vector<map<NodeType, double> > edges;	//Stores node and connected edges
	vector<pair<NodeType, double> > identifyNeighbours(const NodeType &node);	
};

//Returns total number of nodes in graph
template <typename NodeType>
int Graph<NodeType>::numberOfNodes(){
	return mapNodes.size();
}

//Creates node and edge
template <typename NodeType>
void Graph<NodeType>::createNode(const NodeType &node){
	if (checkNodes(node) == 0){
		mapNodes[node] = numberOfNodes();
		vectorNodes.push_back(node);
		map<NodeType, double> tempMap;
		edges.push_back(tempMap);
	}
}

//Return how many times node appears in map
template <typename NodeType>
int Graph<NodeType>::checkNodes(const NodeType &node){
	return mapNodes.count(node);
}

//Takes node number and returns associated name
template <typename NodeType>
NodeType Graph<NodeType>::returnNodeLabel(const int &nodeNum){
	return vectorNodes[nodeNum];
}

//Takes node name and returns associated number
template <typename NodeType>
int Graph<NodeType>::returnNodeNumber(const NodeType &nodeLabel){
	return mapNodes[nodeLabel];
}

//Add edge value to nodes
template <typename NodeType>
double Graph<NodeType>::createEdge(const NodeType &nodeA, const NodeType &nodeB, const double &edgeCost){
	edges[returnNodeNumber(nodeA)][nodeB] = edgeCost;
	return edgeCost;
}

//Identifies neighbouring nodes of node passed in argument
template <typename NodeType>
vector<pair<NodeType, double> > Graph<NodeType>::identifyNeighbours(const NodeType &node){
	vector<pair<NodeType, double> > temp;
	typedef map<NodeType, double>::iterator iter;
	for (unsigned int i = returnNodeNumber(node); i < edges.size(); ++i){
		if (vectorNodes[i]!=node){
			return temp;
		}
		for (iter p = edges[i].begin(); p != edges[i].end() ; ++p){
			temp.push_back(make_pair(p->first, p->second));
		}
	}
	return temp;
}

//Dijkstra's Algorithm: calculates shorts path between startNode and endNodes
template <typename NodeType>
#define pairdef pair<double, NodeType>
vector<pair<double, NodeType> > Graph<NodeType>::dijkstraAlgorithm(const NodeType &startNode, const NodeType &endNode){
	priority_queue<pairdef, vector<pairdef> > Q;	//Priority queue to maintain a sorted list costs/nodes
	vector<pairdef> workingList;					//"List" of nodes/costs to check
	vector<pairdef> finalPath;						//Stores nodes comrpising of shortest path 

	for (signed int i = 0; i < numberOfNodes(); ++i){
		workingList.push_back(make_pair(999, ""));	//Set all nodes as unvisited (cost of 999)
	}
	if (startNode == endNode){
		return finalPath;	//No Path
	}

	workingList[returnNodeNumber(startNode)].first = 0;
	workingList[returnNodeNumber(startNode)].second = startNode;
	Q.push(pairdef(workingList[returnNodeNumber(startNode)].first, startNode));

	while (!Q.empty()){
		NodeType tempNode = Q.top().second;
		Q.pop();
		if (endNode == tempNode){
			continue;
		}
		vector<pair<NodeType, double> > neighbours = identifyNeighbours(tempNode);	
		typedef vector<pair<NodeType, double> >::iterator iter;			
		for (iter p = neighbours.begin(); p != neighbours.end() ; ++p){		//For each neighbour of the temp node
			NodeType neighbourNode = p->first;
			double cost;
			cost = p->second;
			if (workingList[returnNodeNumber(neighbourNode)].first > workingList[returnNodeNumber(tempNode)].first + cost){		//If cost of neighbouring node is greater than the temp node + cost, add to the queue
				workingList[returnNodeNumber(neighbourNode)].first = workingList[returnNodeNumber(tempNode)].first + cost;	
				workingList[returnNodeNumber(neighbourNode)].second = tempNode;				
				Q.push(pairdef( workingList[returnNodeNumber(neighbourNode)].first, neighbourNode));
			}
		}
	}
	if (workingList[returnNodeNumber(endNode)].first == 999){
		return finalPath;	//No Path
	}

	int n = returnNodeNumber(endNode);
	finalPath.push_back(make_pair((workingList[n].first)-1, workingList[n].second));
	finalPath.push_back(make_pair((workingList[n].first), endNode));	
	while(workingList[n].first!=1){
		n = returnNodeNumber(workingList[n].second);
		finalPath.push_back(make_pair((workingList[n].first)-1, workingList[n].second));
	}
	sort(finalPath.begin(), finalPath.end());
	return finalPath;
}

//Read in .txt file containing graph (formatted: NodeA NodeB Cost)
template <typename NodeType>
void read_graph(Graph<NodeType> &g, const string &filePath){
	ifstream inFile;
	NodeType tempA, tempB;
	double i;
	inFile.open(filePath);
	while (inFile >> tempA  >> tempB >> i){
		g.createNode(tempA);
		g.createNode(tempB);
		g.createEdge(tempA, tempB, i);
	}
}

//Main reads in graph from specified file path, receives user input for start/end nodes (performs check to see if nodes exist), then generates and returns path
int main(){
	cout << "C++ Coursework - Blair Trusler" << endl;
	Graph<string> graph;
	vector<pair<double, string> > thePath;
	string startNode, endNode;
	string filePath = "C:\\Users\\Blair\\Dropbox\\CGT Personal\\C++\\Coursework\\Debug\\graph2.txt";		//INSERT FILE PATH HERE
	read_graph(graph, filePath);
	cout << endl << endl;

	cout << "Total number of nodes in graph: " << graph.numberOfNodes() << endl << endl;
	cout << "Enter Start Node: ";
	cin >> startNode;
	cout << "Enter End Node: ";
	cin >> endNode;
	
	if (graph.checkNodes(startNode)==0){
		cout << "Node: '" << startNode << "' does not exist in graph" << endl;
	}
	if (graph.checkNodes(endNode)==0){
		cout << "Node: '" << endNode << "' does not exist in graph" << endl;
	}

	if ((graph.checkNodes(startNode) != 0) && (graph.checkNodes(endNode) != 0)){
		thePath = graph.dijkstraAlgorithm(startNode, endNode);
		if (thePath.size() == 0){
			cout << "No Path Found" << endl;
		}
		else{
			typedef vector<pair<double, string> >::iterator iter;
			for (iter p = thePath.begin(); p != thePath.end() ; ++p){
				cout << p->first << " " << p->second << endl;
			}
		}
	}
	system("pause");
}